#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣53. 最大子数组和
// 【难度】简单
// 【提交】2025.10.09 https://leetcode.cn/problems/maximum-subarray/submissions/669090881/
// 【标签】动态规划；分治；数组
class Solution_LC0053 {
public:
    int maxSubArray(vector<int>& nums) {
        int maxS = nums[0];
        int sum = 0;
        for(int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            maxS = max(maxS, sum);
            if(sum < 0) {
                sum = 0;
            }
        }
        return maxS;
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组nums，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 模型：动态规划（Kadane算法），通过维护当前子数组和和全局最大值来解决问题。
 * 
 * 二、标准解法状态设计
 * 1. 使用变量sum记录当前子数组和，maxS记录全局最大和。
 * 2. 遍历数组，对于每个元素，将其加入当前子数组和。
 * 3. 更新全局最大和。
 * 4. 如果当前子数组和变为负数，则重置为0（因为负数会降低后续子数组的和）。
 * 
 * 三、你的实现思路
 * 使用Kadane算法，在一次遍历中计算最大子数组和。
 * 通过维护当前子数组和和全局最大值，避免了暴力枚举所有子数组。
 * 
 * 四、逐行注释（带细节提醒）
 * int maxS = nums[0]; // 初始化全局最大值
 * int sum = 0; // 初始化当前子数组和
 * 
 * for(int i = 0; i < nums.size(); ++i) { // 遍历数组
 *     sum += nums[i]; // 更新当前子数组和
 *     maxS = max(maxS, sum); // 更新全局最大值
 *     if(sum < 0) { // 如果当前子数组和为负数
 *         sum = 0; // 重置当前子数组和
 *     }
 * }
 * return maxS; // 返回最大子数组和
 * 
 * 五、正确性证明
 * Kadane算法的正确性基于：任何负和的子数组都不可能是最大和子数组的前缀。
 * 因此，当当前子数组和变为负数时，可以安全地重置为0，从下一个元素重新开始计算。
 * 
 * 六、复杂度
 * 时间：O(n)，只需遍历数组一次。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 空间复杂度低，无需额外数组；
 *   - 代码简洁，实现高效。
 * 缺点：
 *   - 算法理解起来有一定难度；
 *   - 无法直接获取最大子数组的起始和结束位置。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.empty()) return 0;
 * 2. 可以扩展算法以记录最大子数组的起始和结束位置；
 * 3. 对于教学场景，可以添加注释解释Kadane算法的原理。
 * 
 * 九、一句话总结
 * Kadane算法是解决"最大子数组和"问题的经典方法，你的实现简洁高效，
 * 展现了动态规划思想在解决最优化问题中的应用。
 */